/********************************************
Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Subscribe to see which companies asked this question
********************************************/
#include <stdio.h>
#include <stdlib.h>

struct ListNode{
	int val;
	struct ListNode* next;
};

void setList(struct ListNode* head, int val)
{
	struct ListNode *q;
	q = head;
	while(q->next != NULL)
		q = q->next;
	
	struct ListNode *tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
	if(tmp == NULL)
		return;
	tmp->val = val;
	tmp->next = q->next;
	q->next = tmp;
}

void print(struct ListNode* head)
{
	struct ListNode* p;
	for(p = head; p != NULL; p = p->next)
	{
		printf("[%d]", p->val);
	}
	printf("\n");
}

struct ListNode* partition(struct ListNode* head, int x) {
	if(head == NULL || head->next == NULL)
		return head;
	struct ListNode *pSmall = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode *pGreat = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode *pCur, *pPreSml, *pPreGre;
	pCur = head;
	pSmall->next = NULL;
	pGreat->next = NULL;
	pPreSml = pSmall;
	pPreGre = pGreat;

	while(pCur != NULL)
	{
		if(pCur->val < x)
		{
			pPreSml->next = pCur;
			pPreSml = pPreSml->next;
		}
		else
		{
			pPreGre->next = pCur;
			pPreGre = pPreGre->next;
		}
		pCur = pCur->next;
	}
	pPreGre->next = NULL;
	if(pSmall->next != NULL)
		pPreSml->next = pGreat->next;
	else
		pSmall->next = pGreat->next;
	return pSmall->next;
}

void main(void)
{
	struct ListNode* head;
	int num[] = {2,1};
	int i;
	int val = 2;
	head = (struct ListNode*)malloc(sizeof(struct ListNode));
	head->next = NULL;
	head->val = num[0];
	for(i = 1; i < sizeof(num)/sizeof(int); i++)
		setList(head, num[i]);
	print(head);
	print(partition(head,val));
}

